package 代码随想录_动态规划.子序列问题.连续;

/**
 * @author zx
 * @create 2022-06-05 16:58
 * 组成部分一：确定状态
 *               最后一步：
 *               子问题：
 *               确定dp数组(dp table)以及下标的含义
 *               dp[i]：包括下标i之前的最大连续子序列和为dp[i]。
 * 组成部分一：确定状态
 * 最后一步：
 * 子问题：
 * 组成部分二：转移方程
 * dp[i]只有两个方向可以推出来：
 *      dp[i - 1] + nums[i],即：nums[i]加入当前连续子序列和
 *      nums[i],即：从头开始计算当前连续子序列和
 * 一定是取最大的,所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
 * 组成部分三：初始条件和边界情况
 * 从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态,dp[0]就是递推公式的基础
 * 根据dp[i]的定义,很明显dp[0]因为为nums[0]即dp[0] = nums[0].
 * 组成部分四：计算顺序
 */
public class 最大子序和_53 {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];//注意这里，必须设置为dp[0],设置为0会报错
        for(int i = 1;i < nums.length;i++){
            //不加入nums[i],即：从头开始计算当前连续子序列和
            //加入num[i]：dp[i - 1] + nums[i],即：nums[i]加入当前连续子序列和
            dp[i] = Math.max(nums[i],dp[i - 1] + nums[i]);
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}
